package 平衡二叉树;

public class Solution {
    // 给定一个二叉树，判断它是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return isBalanced1(root) != -1;
    }

    public int isBalanced1(TreeNode root) {
        // 递归 时间复杂度：O(n) 空间复杂度O(n)
        // 参数：root 返回值：leftLevel == -1 || rightLevel == -1 || Math.abs(leftLevel - rightLevel) > 1 或者返回Math.max(leftLevel, rightLevel) + 1;
        // 终止条件：root == null
        // 单层递归逻辑：遍历左右子树，统计左右子树的树高，然后计算差值
        if (root == null) {
            return 0;
        }
        int leftLevel = isBalanced1(root.left);
        int rightLevel = isBalanced1(root.right);
        if (leftLevel == -1 || rightLevel == -1 || Math.abs(leftLevel - rightLevel) > 1)
            return -1;
        return Math.max(leftLevel, rightLevel) + 1;
    }
}
